package sjjg.tree;

public class IndexMinPriorityQueue<T extends Comparable> {//索引最小优先队列
    private T[]heap;
    private int[]pq;
    private int[] qp;
    private int N;
    public IndexMinPriorityQueue(int capacity){
        heap=(T[])new Comparable[capacity+1];
        pq=new int[capacity+1];
        qp=new int[capacity+1];
        //让qp的所有值初始化为-1
        for (int i = 0; i < qp.length; i++) {
            qp[i]=-1;
        }
        N=0;
    }
    public boolean less(int index1,int index2){

        return heap[pq[index1]].compareTo(heap[pq[index2]])<0;
    }
    public void exchange(int index1,int index2){
                //交换pq两索引位置的值
                int temp;
                temp=pq[index1];
                pq[index1]=pq[index2];
                pq[index2]=temp;
                //调整qp
                 qp[pq[index1]]=index1;
                 qp[pq[index2]]=index2;
    }
    public int delMin(){
        //记录heap中最小值的索引
        int minIndex=pq[1];
        //交换pq 1处的索引的值与N处的索引的值；
        exchange(1,N);
        //删除pq N 处索引的值
        pq[N]=-1;
        //调整qp
        qp[minIndex]=-1;
        //给原数组被删除元素位置空
        heap[minIndex]=null;
        //元素个数--
        N--;
        //对pq做下沉处理 使pq重新有序
        sink(1);
        return minIndex;//放回被删除元素所在的索引
    }
    public void insert(int index,T t){
           if(contains(index)){
               return;
           }
           heap[index]=t;
           pq[++N]=index;
           //调整qp
           qp[index]=N;
           //对pq进行堆调整
           swim(N);
    }
    private void swim(int k){
        while (k>1){
             if(less(k,k/2)){
                 exchange(k,k/2);
             }else {
                 break;
             }
             k=k/2;
        }
    }
    private void sink(int k){
        int min=0;
        while (2*k<=N){
              if(2*k+1<=N){
                  if(less(2*k,2*k+1)){
                      min=2*k;
                  }else {
                      min=2*k+1;
                  }
              }else {
                  min=2*k;
              }

              if(less(min,k)){
                  exchange(min,k);
              }else {
                  break;
              }
              k=min;
        }
    }
    public int size(){
        return N;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public boolean contains(int index){
        if(qp[index]!=-1){
            return true;
        }
        return false;
    }
    public void changeItem(int index,T t){
           if(!contains(index)){
              return;
           }
           //改变索引index的值
          heap[index]= t;
           //通过index找到pq的索引
           int now=qp[index];
           //对pq进行堆调整
           swim(now);
           sink(now);
    }
    public int minIndex(){
        return pq[1];
    }
    public void delete(int index){
           if(!contains(index)){
               return;
           }
           //让index处元素置空
          heap[index]=null;
           //暂存被删除元素在pq中的索引
           int k=qp[index];
           //让该元素置于尾部进行删除
           exchange(qp[index],N);
          //调整qp
          qp[pq[N]]=-1;
          //删除pq尾部元素
          pq[N]=-1;
          //元素个数-1
          N--;
          //堆pq进行堆调整
          swim(k);
          sink(k);
    }

    public static void main(String[] args) {
        IndexMinPriorityQueue<String> indexMinPriorityQueue = new IndexMinPriorityQueue<>(10);
        indexMinPriorityQueue.insert(1,"A");
        indexMinPriorityQueue.insert(2,"B");
        indexMinPriorityQueue.insert(3,"C");
        indexMinPriorityQueue.insert(4,"D");
        indexMinPriorityQueue.insert(5,"E");
        indexMinPriorityQueue.insert(6,"F");
        indexMinPriorityQueue.changeItem(2,"G");
        indexMinPriorityQueue.delete(1);
        while (!indexMinPriorityQueue.isEmpty()){
            int min = indexMinPriorityQueue.delMin();
            System.out.print(min+" ");
        }
    }
}
